package bs;

import java.util.Arrays;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2023-01-05
 * Time: 21:35
 */
//二分法最常见的应用就是查找某个元素是否存在
public class BSExist {
    //要测试的方法
    public static boolean bsexist(int[] arr,int target){
        if(arr==null || arr.length<1){
            return false;
        }
        int l=0;
        int r=arr.length-1;
        int mid=-1;
        while (l<r){
            mid=l+((r-l)>>1);
            if(arr[mid]==target){
                return true;
            }else if(arr[mid]<target){
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        return arr[l]==target;
    }
    
    //对数器，一定对的方法
    public static boolean comparator(int[] arr,int target){
        for (int num: arr) {
            if(num==target) return true;
        }
        return false;
    }
    //对数器最重要的就是生成随机样本数组
    public static int[] generateRandomArray(int maxSize,int maxValue){
        //给定一个数组的最大长度和数组元素的最大值，利用random的随机性和等概率性生成随机值有正有负
        int[] arr=new int[(int)((maxSize+1)*Math.random())];  //生成0~maxsize长度的数组
        //赋予随机值
        // Math.random()   [0,1)
        // Math.random() * N  [0,N)
        // (int)(Math.random() * N)  [0, N-1]
        // (int)(Math.random() * N+1)  [0, N]
        for(int i=0;i<arr.length;i++){
            arr[i]=(int) ((maxValue+1) * Math.random())- (int) ((maxValue) *Math.random());
        }
        return arr;
    }
    
    //进行大数量的测试
    public static void main(String[] args) {
        int testTime=500000;
        int maxSize=100;
        int maxValue=100;
        //所有样本测试成功为true
        boolean accepted=true;
        for(int i=0;i<testTime;i++){
            int[] arr=generateRandomArray(maxSize,maxValue);
            //二分法大部分基于有序
            Arrays.sort(arr);
            //给定随机的要查找的值
            int target=(int) (Math.random() * (maxValue+1)) - (int) (Math.random() * (maxSize));
            //让我们要测试的方法和一定对的方法比较结果
            if(comparator(arr,target) != bsexist(arr,target)){
                accepted=false;
                break;
            }
        }
        System.out.println(accepted ? "Nice!" : "Error!");
    }
}
